int binarySearch(int* nums, int numsSize, int target, bool lower) {
    int left = 0, right = numsSize - 1, ans=numsSize;
   //采用二分法进行查找
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            //当两者相等时，令right=mid-1，之后mid一定为mid-1即下一次判断的是本元素的左边元素
            //如判断相等，若左边元素仍等于target，则继续向左偏移，若不相等，则left++，判断其右边的第一个元素，
            //最后mid==与<的交界处来回偏移，直到left>right，此时第一个相等的下标在ans中保存
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

int search(int* nums, int numsSize, int target) {
    //寻找第一个等于target的下标，存在返回下标，不存在返回numsSize
    int leftIdx = binarySearch(nums, numsSize, target, true);
    //寻找第一个大于target的下标，存在返回下标，不存在返回numsSize
    int rightIdx = binarySearch(nums, numsSize, target, false);
    int ret = 0;
    //若存在匹配targer的元素，该元素下标一定小于rightIdx（无论rightIdx是否存在),不需要进行if判断
    //若存在leftIdx，同时存在rightIdx，则结果为两者相减
    //若存在leftIdx，但不存在rightIdx，则rightIdx为numsSize，即数组最右侧元素一定等于target，则结果仍为两者相减
    //因此条件判断中只要保证leftIdx存在即可
    if (leftIdx !=numsSize) {
        ret = rightIdx - leftIdx;
    }
    return ret;
}
